// 展开方式为 二叉树的先序遍历
// 1. 将左子树插入到右子树的地方
// 2. 将原来的右子树接到左子树的最右边节点
// 3. 考虑新的右子树的根节点，一直重复上边的过程，直到新的右子树为 null
var flatten = function (root) {
  while (root !== null) {
    // 左子树为 null 直接考虑下一个节点
    if (root.left == null) {
      root = root.right;
    } else {
      // 找左子树最右边的节点
      let pre = root.left;
      while (pre.right !== null) {
        pre = pre.right;
      }
      // 将原来的右子树接到左子树的最右边节点
      pre.right = root.right;
      // 将左子树插入到右子树的地方
      root.right = root.left;
      root.left = null;
      // 考虑下一个节点
      root = root.right;
    }
  }
};
